package oj;

import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

/**
 * @author chaolong.jin
 * @description
 * @date 2019/08/07 16:29
 */
public class Sort {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (true) {

            int n = scanner.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = new Random().nextInt(n);
                System.out.print(a[i] + " ");
            }

            System.out.println();
            quickSort(a, 0, a.length - 1);
            System.out.println(Arrays.toString(a));
        }
    }

    public static void quickSort(int[] a, int left, int right) {
        if (left < right) {
            int i = sort(a, left, right);
//            System.out.println(Arrays.toString(a)+"==="+i+"==left+"+left+"   right="+right);
//            System.out.println("left=" + left + "     right=" + right);
            quickSort(a, left, i-1);
            quickSort(a, i+1 , right);
        }

    }

    /**
     * 指针替换
     *
     * @param a
     * @param left
     * @param right
     * @return
     */
//    public static int sort(int[] a, int left, int right) {
//        int cursor = left;
//        int i = left;
//        int j = right;
//        while (i < j) {
//            while (a[j] >= a[cursor] && i < j) {
//                j--;
//            }
//            while (a[i] < a[cursor] && i < j) {
//                i++;
//            }
//            if (i < j) {
//                swap(a, i, j);
//            }
//        }
//        swap(a, cursor, j);
//        return i;
//    }
    public static int sort(int[] a, int left, int right) {
        int cursor = left;
        int i = left;
        int j = right;
        int result = a[cursor];
        while (i < j) {
            while (i < j && a[j] >result) {
                j--;
            }
            if (i < j) {
                a[cursor] = a[j];
                cursor = j;
                i++;
            }
            while (i < j && a[i] < result) {
                i++;
            }
            if (i < j) {
                a[cursor] = a[i];
                cursor = i;
                j--;
            }

        }
        a[cursor] = result;
        return cursor;
    }
//    public static int sort(int[] a, int low, int height) {
//        int cursor = low;
//        int start = low;
//        int end = height;
//        while (start < end) {
//            while (a[end] > a[cursor] && start <= end) {
//                end--;
//            }
//            if (a[end] < a[cursor]) {
//                swap(a, end, cursor);
//                break;
//            }
//            start++;
//            while (a[start] < a[cursor] && start <= end) {
//                start++;
//            }
//            if (a[start] > a[cursor]) {
//                swap(a, end, cursor);
//                break;
//            }
//
//        }
//        if (start > low) {
//            sort(a, start, cursor - 1);
//        }
//        if(end<height){
//            sort(a, end+1, height);
//        }
//        return start;
//    }

    private static void swap(int[] arrays, int a, int b) {
        int temp = arrays[a];
        arrays[a] = arrays[b];
        arrays[b] = temp;
    }
}
